package star.位运算.数组中数字出现的次数;

public class SingleNumbers {
    public static void main(String[] args) {
        System.out.println(new SingleNumbers().singleNumber(new int[]{8, 8, 8, 6, 5, 5, 5}));
    }
    public int[] singleNumbers(int[] nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)               // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)               // 2. 循环左移，计算 m
            m <<= 1;
        for(int num: nums) {              // 3. 遍历 nums 分组
            if((num & m) != 0) x ^= num;  // 4. 当 num & m != 0
            else y ^= num;                // 4. 当 num & m == 0
        }
        return new int[] {x, y};          // 5. 返回出现一次的数字
    }

    public int[] singleNumbers2(int[] nums) {
        int eor = 0;
        for(int num : nums)
            eor ^= num;
        //提取出最右边的一个1
        int rightOne = eor & (~eor + 1);
        int onlyOne = 0;
        for (int cur : nums){
            if ((cur & rightOne) == rightOne){
                onlyOne ^= cur;
            }
        }
        return new int[] {onlyOne, onlyOne^eor};
    }

    public int singleNumber(int[] nums) {
        int[] counts = new int[32];
        for(int num : nums) {
            for(int i = 0; i < 32; i++) {
                counts[i] += num & 1; // 更新第 i 位 1 的个数之和
                num >>= 1;            // 第 i 位 --> 第 i 位
            }
        }
        int res = 0, m = 3;
        for(int i = 5; i >= 0; i--) {
            res <<= 1;
            res |= counts[i] % m;     // 恢复第 i 位

        }
        return res;
    }
}
